package week_08;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 1584. 连接所有点的最小费用
 * 给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。
 * <p>
 * 连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
 * <p>
 * 请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * <p>
 * 输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
 * 输出：20
 * 解释：
 * <p>
 * 我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
 * 注意到任意两个点之间只有唯一一条路径互相到达。
 * 示例 2：
 * <p>
 * 输入：points = [[3,12],[-2,5],[-4,1]]
 * 输出：18
 * 示例 3：
 * <p>
 * 输入：points = [[0,0],[1,1],[1,0],[-1,1]]
 * 输出：4
 * 示例 4：
 * <p>
 * 输入：points = [[-1000000,-1000000],[1000000,1000000]]
 * 输出：4000000
 */
public class MinCostConnectPoints_1584 {
    int[] jointSet;

    public int minCostConnectPoints(int[][] points) {
        /**
         *          kruskal算法 使用并查集
         *          每次连最小的边，如果相同则跳过，如果链接新点
         *          处理两点的之间两两距离
         *          points 先排序 取index代表点
         *
         *
         */
        //处理边组
        int n = points.length;
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                // 曼哈顿距离 ：|xi - xj| + |yi - yj|
                edges.add(new int[]{i, j, Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1])})
        ;
        edges.sort((o1, o2) -> {
            return o1[2] - o2[2];
        });
        jointSet = new int[n];
        for (int i = 0; i < n; i++) jointSet[i] = i;
        // 开始链接边
        int ans = 0;
        for (int i = 0; i < edges.size(); i++) {
            int x = edges.get(i)[0];
            int y = edges.get(i)[1];
            int z = edges.get(i)[2];
            if (find(x) != find(y)) {
                jointSet[find(y)] = find(x);
                ans += z;
            }
        }
        return ans;
    }

    public int find(int x) {
        return (x == jointSet[x]) ? x : (jointSet[x] = find(jointSet[x]));
    }

    public static void main(String[] args) {
        //[[0,0],[2,2],[3,10],[5,2],[7,0]]
        int[][] points = new int[][]{{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}};
        MinCostConnectPoints_1584 test = new MinCostConnectPoints_1584();
        int ans = test.minCostConnectPoints(points);
        System.out.println(ans);

    }
}
